package 困难.动态规划.状态压缩;

/**
 * 给你 nums ，它是一个大小为 2 * n 的正整数数组。你必须对这个数组执行 n 次操作。
 * 在第 i 次操作时（操作编号从 1 开始），你需要：
 * 选择两个元素 x 和 y 。
 * 获得分数 i * gcd(x, y) 。
 * 将 x 和 y 从 nums 中删除。
 * 请你返回 n 次操作后你能获得的分数和最大为多少。
 * 函数 gcd(x, y) 是 x 和 y 的最大公约数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximize-score-after-n-operations
 */
public class N次操作后的最大分数和_1799 {

    public static void main(String[] args) {

        System.out.println(Integer.toBinaryString(300));
        System.out.println(Integer.toBinaryString(300 - (1 << 2)));

        System.out.println(gcd(5, 5));

        System.out.println(new N次操作后的最大分数和_1799().maxScore(new int[]{
                3, 4, 6, 8
        }));

    }

    /**
     * 动态规划+预处理
     * 先预处理保存两数的最大公约数 record[i][j] 表示 gcd(nums[i],nums[j])
     * <p>
     * 1表示未删除，0表示已删除，初始状态为 000000，表示全部已删除，没有
     * 需要删除的元素得分为0，当遍历到 3 时，即 000011 时，他的状态是由 000000 添加
     * 两个元素得到，dp[i] 表示 i 的二进制表示的状态得到的最大和分数是多少
     * dp[3]=dp[0]+ 1是数量/2*gcd(nums[0],nums[1])
     * 001111 <-- 001100,000011,...
     */
    public int maxScore(int[] nums) {
        int[][] record = new int[nums.length][nums.length];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                record[i][j] = gcd(nums[i], nums[j]);
                record[j][i] = record[i][j];
            }
        }

        int[] dp = new int[1 << nums.length];
        for (int state = 0; state < dp.length; state++) {
            int cnt = Integer.bitCount(state);
            if (cnt % 2 == 0) {
                for (int i = 0; i < nums.length; i++) {
                    if ((state >> i & 1) == 1) {
                        for (int j = i + 1; j < nums.length; j++) {
                            if ((state >> j & 1) == 1) {
                                // state - (1 << i) - (1 << j)
                                // 001111 将其中 i j 的位置变为0
                                dp[state] = Math.max(dp[state], dp[state - (1 << i) - (1 << j)] + cnt / 2 * gcd(nums[i], nums[j]));
                            }
                        }
                    }
                }
            }
        }

        return dp[dp.length - 1];
    }

    // 更相减损法
    private static int gcd(int num1, int num2) {
        if (num1 == num2) return num1;
        int ans = 1;
        while (num1 % 2 == 0 && num2 % 2 == 0) {
            num1 /= 2;
            num2 /= 2;
            ans *= 2;
        }

        int max = Math.max(num1, num2), min = Math.min(num1, num2);
        while (min != max - min) {
            int a = max - min;
            int b = min;
            max = Math.max(a, b);
            min = Math.min(a, b);
        }
        return ans * min;
    }

}
